백준 16287번

Parcel

Posted by ChoiCube84 on August 09, 2024 · 29 mins read
프로그래밍 문제풀이

백준 16287번

오늘 풀어본 문제는 백준의 16287번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 6

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

국제대학소포센터(ICPC: International Collegiate Parcel Center)는 전세계 대학생들을 대상으로 소포 무료 배송 이벤트를 진행하고 있다. 무료 배송 조건은 보낼 소포가 물품 $4$ 개로 구성되어야 하며 이들 물품의 무게 합이 정확히 정해진 정수 무게 $w$ 그램이어야 한다는 것이다.

부산대학교에 있는 찬수는 영국 왕립대학에 있는 수환에게 보낼 물품이 매우 많이 있는데, 각 물품의 무게(모두 정수 그램)는 모두 다르다. 이 이벤트는 한시적으로 진행되는 이벤트이기 때문에 찬수는 자신이 보낼 물품 중에서 이 조건을 만족하는 물품 $4$ 개가 있는지 가능하면 빨리 알아내고 싶다. 다시 말해서 서로 다른 $n$ $(n \le 4)$ 개의 정수로 이루어진 집합 $A$ 에서 $4$ 개의 원소만 꺼내어 만든 부분집합 $B$ $(\vert B \vert = 4)$ 가 $\sum_{b \in B} b = w$ 조건을 만족하는지 판단하려고 한다.

주어진 $w$ 와 $A$ 에 대해서, 위 조건을 만족하는 부분집합 $B$ 가 존재하면 YES를, 아니면 NO를 출력하는 프로그램을 작성하시오.

입력

입력은 표준입력을 사용한다. 입력의 첫 줄에는 무게 $w$ $(10 \le w \le 799,994)$ 와 $A$ 의 원소 개수 $n$ $(4 \le n \le 5,000)$ 이 공백으로 분리되어 주어진다. 다음 줄에는 $A$ 의 원소인 $n$ 개의 정수 $a_i \in A$ $(1 \le i \le n)$ 가 공백으로 분리되어 주어진다. 각 원소 $a_i$ 는 $1$ 이상 $200,000$ 이하이다 $(1 \le a_i \le 200,000)$.

출력

출력은 표준출력을 사용한다. 문제의 조건에 따라 YES나 NO를 한 줄에 출력한다.

풀이과정

1번째 시도

문제를 보고 4개의 물품의 무게의 합을 조사하기 위해, 2개씩 묶은 것들끼리 비교하면 될 것 같다는 생각이 들었다. 이를 위해 MITM 방식을 이용하기로 하였고, 다른 물품들의 조합으로 같은 무게가 나올 수 있기 때문에 std::unordered_multimap 을 활용하기로 하였다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

using ll = long long int;
using ull = unsigned ll;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

bool pairCollide(const pii& A, const pii& B);

int main(void) {
    int w, A;
    cin >> w >> A;
   
    vector<int> items(A, 0);
   
    for (int i=0; i<A; i++) {
        cin >> items[i];
    }
   
    unordered_multimap<int, pii> umap;
   
    for (int i=0; i<A; i++) {
        for (int j=i+1; j<A; j++) {
            umap.insert({items[i] + items[j], make_pair(i, j)});
        }
    }
   
    bool found = false;
   
    for (int i=0; i<A; i++) {
        for (int j=i+1; j<A; j++) {
            auto range = umap.equal_range(w - (items[i] + items[j]));
            
            for (auto it = range.first; it != range.second; ++it) {
                if (!pairCollide(make_pair(i, j), it->second)) {
                    found = true;
                    break;
                }
            }
            
            if (found) break;
        }
        
        if (found) break;
    }
   
    if (found) {
        cout << "YES";
    }
    else {
        cout << "NO";
    }
}

bool pairCollide(const pii& A, const pii& B) {
    return A.first == B.first 
        || A.first == B.second
        || A.second== B.first 
        || A.second == B.second;
}

실행 결과 ‘메모리 초과’ 가 떴다.

2번째 시도

메모리 초과는 역시 unordered map 의 사용으로 인한 것이라고 생각되었다. 당시에 이 문제를 더 붙들만한 시간이 없어 나중에 다시 풀어보기로 하였고, 문제를 푸는 방식을 바꿔보기로 하였다.

전체 물품들을 두 그룹으로 나누고, 각 그룹에서 2개씩 골라 무게를 저장하고, 나머지 그룹에서 2개씩 골라서 나온 무게 중 첫 번째 그룹에서 나온 무게와 합쳐 목표 무게가 나올 수 있는지 확인하는 방식으로 해결해보기로 했다.

코드는 다음과 같이 새로 작성하였다.

#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

int main(void) {
    int w, A;
    cin >> w >> A;
   
    vector<int> items(A, 0);
   
    for (int i=0; i<A; i++) {
        cin >> items[i];
    }
   
    gp_hash_table<int, int> table;
   
    for (int i=0; i<(A/2); i++) {
        for (int j=i+1; j<(A/2); j++) {
            int sum = items[i] + items[j];
            
            if (table.find(sum) == table.end()) {
                table[sum] = 1;
            }
            else {
                table[sum]++;
            }
        }
    }
   
    bool found = false;
   
    for (int i=(A/2); i<A; i++) {
        for (int j=i+1; j<A; j++) {
            int sum = items[i] + items[j];
            
            if (table.find(w - sum) != table.end()) {
                found = true;
                break;
            }
        }
        
        if (found) break;
    }
   
    if (found) {
        cout << "YES";
    }
    else {
        cout << "NO";
    }
    
    return 0;
}

실행 결과 ‘틀렸습니다’ 가 떴다.

3번째 시도

문제 풀이 방식에는 틀린 것이 없다고 생각했고, 오버플로우 문제인 것 같아 int 대신 long long int 형을 사용하기로 하였다.

코드는 다음과 같이 수정하였다.

#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

using ll = long long int;

int main(void) {
    ll w, A;
    cin >> w >> A;
   
    vector<ll> items(A, 0);
   
    for (int i=0; i<A; i++) {
        cin >> items[i];
    }
   
    gp_hash_table<ll, ll> table;
   
    for (int i=0; i<(A/2); i++) {
        for (int j=i+1; j<(A/2); j++) {
            ll sum = items[i] + items[j];
            
            if (table.find(sum) == table.end()) {
                table[sum] = 1;
            }
            else {
                table[sum]++;
            }
        }
    }
   
    bool found = false;
   
    for (int i=(A/2); i<A; i++) {
        for (int j=i+1; j<A; j++) {
            ll sum = items[i] + items[j];
            
            if (table.find(w - sum) != table.end()) {
                found = true;
                break;
            }
        }
        
        if (found) break;
    }
   
    if (found) {
        cout << "YES";
    }
    else {
        cout << "NO";
    }
    
    return 0;
}

실행 결과 ‘틀렸습니다’ 가 떴다.

4번째 시도

지금와서 보면, 제대로 고려하지 않은 사항이 너무나도 많은 풀이법이지만, 당시에는 이상한 점을 느끼지 못했고 이 문제의 풀이를 중단했었다. 2, 3번째 시도의 방식의 문제점은, 유일한 방법이 한 그룹에서 4개를 고르거나, 한 그룹에서 3개와 나머지 그룹에서 1개를 고르는 방식으로 구성되는 경우를 제대로 처리할 수 없다는 점이었다.

결국 이 문제를 풀어내기 위해 다른 사람들이 이용한 방식을 찾아보았는데, 내가 문제에서 한 가지 생각하지 못한 부분이 있었다. 그것은 모든 물품의 무게가 다르다는 것이었다. 이 점을 이용하면 첫 번째 풀이에서 사용한 방식을 이용할 수 있었다. 단, 가능한 모든 조합을 저장하는 것이 아닌, 딱 하나만 저장해도 되는 것이었다!

코드는 다음과 같이 새로 작성하였다.

#include <bits/extc++.h>

using namespace __gnu_pbds;
using namespace std;

using ll = long long int;
using ull = unsigned long long int;

using pll = pair<ll, ll>;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	ll w, n;
	cin >> w >> n;

	vector<ll> A(n);
	for (ll i=0; i<n; i++) {
		cin >> A[i];
	}

	gp_hash_table<ll, pll> table;
	
	for (ll i=0; i<n; i++) {
		for (ll j=i+1; j<n; j++) {
			ll sum = A[i] + A[j];
			if (table.find(sum) == table.end()) {
				table[sum] = make_pair(i, j);
			}
		}
	}
	
	for (ll i=0; i<n; i++) {
		for (ll j=i+1; j<n; j++) {
			ll sum = A[i] + A[j];
			if (table.find(w - sum) != table.end()) {
				cout << "YES";
				return 0;
			}
		}
	}

	cout << "NO";
	
	return 0;
}

실행 결과 ‘틀렸습니다’ 가 떴다.

5번째 시도

틀린 원인으로 조합을 검사하는 과정에서, 물품이 중복되었는지 확인하는 코드를 작성하는 것을 깜빡했다는 것을 금방 발견할 수 있었다.

코드는 다음과 같이 수정하였다.

#include <bits/extc++.h>

using namespace __gnu_pbds;
using namespace std;

using ll = long long int;
using ull = unsigned long long int;

using pll = pair<ll, ll>;

bool pairCollide(const pll& a, const pll& b);

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	ll w, n;
	cin >> w >> n;

	vector<ll> A(n);
	for (ll i=0; i<n; i++) {
		cin >> A[i];
	}

	gp_hash_table<ll, pll> table;
	
	for (ll i=0; i<n; i++) {
		for (ll j=i+1; j<n; j++) {
			ll sum = A[i] + A[j];
			if (table.find(sum) == table.end()) {
				table[sum] = make_pair(i, j);
			}
		}
	}
	
	for (ll i=0; i<n; i++) {
		for (ll j=i+1; j<n; j++) {
			ll sum = A[i] + A[j];
			if (table.find(w - sum) != table.end() && !pairCollide(table[w - sum], make_pair(i, j))) {
				cout << "YES";
				return 0;
			}
		}
	}

	cout << "NO";
	
	return 0;
}

bool pairCollide(const pll& a, const pll& b) {
	if (a.first == b.first || a.first == b.second || a.second == b.first || a.second == b.second) {
		return true;
	}
	else {
		return false;
	}
}

실행 결과 ‘시간 초과’ 가 떴다.

6번째 시도

시간 초과의 원인으로, 알고리즘이 문제가 있는 것 같지는 않았다. 그냥 gp_hash_table 자체가 느려서 발생하는 문제일 것이라고 생각했다. 그렇다면 대체 std::unordered_map은 얼마나 느리다는 것인가…

그래서 해시 테이블 대신 std::vector 를 활용하여 무게들을 저장하기로 하였다.

코드는 다음과 같이 작성하였다.

#include <bits/extc++.h>

using namespace __gnu_pbds;
using namespace std;

using ll = long long int;
using ull = unsigned long long int;

using pll = pair<ll, ll>;

bool pairCollide(const pll& a, const pll& b);

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	ll w, n;
	cin >> w >> n;

	vector<ll> A(n);
	for (ll i=0; i<n; i++) {
		cin >> A[i];
	}

	vector<pll> combinations(400001);
	
	for (ll i=0; i<400001; i++) {
	    combinations[i].first = -1;
	}

	for (ll i=0; i<n; i++) {
		for (ll j=i+1; j<n; j++) {
			combinations[A[i] + A[j]] = make_pair(i, j);
		}
	}

	for (ll i=0; i<n; i++) {
		for (ll j=i+1; j<n; j++) {
			ll sum = A[i] + A[j];
			
			if (sum <= w && !(combinations[w - sum].first == -1) && !pairCollide(combinations[w - sum], make_pair(i, j))) {
				cout << "YES";
				return 0;
			}
		}
	}

	cout << "NO";

	return 0;
}

bool pairCollide(const pll& a, const pll& b) {
	if (a.first == b.first || a.first == b.second || a.second == b.first || a.second == b.second) {
		return true;
	}
	else {
		return false;
	}
}

실행 결과 ‘런타임 에러 (OutOfBounds)’ 가 떴다.

7번째 시도

수정 과정에서 코드 복사를 잘못해서 컴파일 정상적으로 되도록 고치기 이전의 코드를 붙여넣기 해버렸다. 당연하게도 실행 결과 ‘컴파일 에러’ 가 떴다. 어이 없게 글 분량만 늘어났다…

8번째 시도

6번째 시도에서 발생한 런타임 에러는 OutOfBounds 였다. 그래서 뭔가 std::vector 에서 접근 오류가 발생한 것 같아 그냥 저장 용량을 늘려줘봤다.

코드는 다음과 같이 수정하였다.

#include <bits/extc++.h>

using namespace __gnu_pbds;
using namespace std;

using ll = long long int;
using ull = unsigned long long int;

using pll = pair<ll, ll>;

bool pairCollide(const pll& a, const pll& b);

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	ll w, n;
	cin >> w >> n;

	vector<ll> A(n);
	for (ll i=0; i<n; i++) {
		cin >> A[i];
	}

	vector<pll> combinations(800001);
	
	for (ll i=0; i<800001; i++) {
	    combinations[i].first = -1;
	}

	for (ll i=0; i<n; i++) {
		for (ll j=i+1; j<n; j++) {
			combinations[A[i] + A[j]] = make_pair(i, j);
		}
	}

	for (ll i=0; i<n; i++) {
		for (ll j=i+1; j<n; j++) {
			ll sum = A[i] + A[j];
			
			if (sum <= w && !(combinations[w - sum].first == -1) && !pairCollide(combinations[w - sum], make_pair(i, j))) {
				cout << "YES";
				return 0;
			}
		}
	}

	cout << "NO";

	return 0;
}

bool pairCollide(const pll& a, const pll& b) {
	if (a.first == b.first || a.first == b.second || a.second == b.first || a.second == b.second) {
		return true;
	}
	else {
		return false;
	}
}

그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.

마무리

백준 1006번 (습격자 초라기) 급은 아니지만, 이 문제도 풀어내는데 나름 오래걸린 문제였고, CLASS 6 문제를 모두 풀어내기 위해서는 반드시 거쳐야하는 관문이었기 때문에, 풀어내고 나서 굉장히 홀가분한 기분이 들었다.

이번 문제에서 충격적이었던 부분은, 물품의 무게가 모두 달라 가능한 여러 조합 중 하나만 저장해도 된다는 것이었다. 사실 이걸 떠올리는 것과 MITM 을 이용하는 것이 이 문제의 핵심이었던 것 같은데, MITM 은 쉽게 떠올렸어도 하나만 저장해도 된다는 것은 전혀 상상도 못했기 때문이다. 첫 번째 시도에서 std::unordered_map 이 아닌 std::unordered_multimap 을 이용한 것도 그런 이유였다.

앞으로는 이런 식으로 핵심 아이디어들을 끄집어낼 수 있는 능력이 중요할 것 같은데, 아직 준비가 잘 안된 것 같아 걱정스러워지기 시작했다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/16287

← Previous Post Next Post →